package daily.oct;

import java.util.LinkedList;
import java.util.Queue;

public class lc778 {
    /*
     * 这个问题可以理解为：
    我们要找最小的 T，使得在时间 T 时，存在一条从 (0,0) 到 (N-1,N-1) 的路径，路径上所有格子的高度都不超过 T。
     */

     // 四个方向：上、右、下、左
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    public int swimInWater(int[][] grid) {
        int n = grid.length;

        // 二分查找的上下界
        int left = grid[0][0]; // 至少要从起点的高度开始
        int right = n * n - 1; // 题目保证高度在 [0, n*n-1] 范围内

        while (left < right) {
            int mid = left + (right - left) / 2;

            // 检查在时间 mid 时是否能到达终点
            if (canReachEnd(grid, mid)) {
                right = mid; // mid 可行，尝试更小的时间
            } else {
                left = mid + 1; // mid 不可行，需要更大的时间
            }
        }

        return left;
    }
    
    // 检查在时间 T 时是否能从起点到达终点
    private boolean canReachEnd(int[][] grid, int T) {
        int n = grid.length;

        // 如果起点或终点的高度就大于 T，直接返回 false
        if (grid[0][0] > T || grid[n - 1][n - 1] > T) {
            return false;
        }

        boolean[][] visited = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();

        // 从起点开始 BFS
        queue.offer(new int[] { 0, 0 });
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];

            // 到达终点
            if (x == n - 1 && y == n - 1) {
                return true;
            }

            // 遍历四个方向
            for (int[] dir : DIRECTIONS) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                // 检查新位置是否在网格内、未被访问、且高度不超过 T
                if (nx >= 0 && nx < n && ny >= 0 && ny < n
                        && !visited[nx][ny] && grid[nx][ny] <= T) {
                    visited[nx][ny] = true;
                    queue.offer(new int[] { nx, ny });
                }
            }
        }

        return false; // 无法到达终点
    }
    
    public static void main(String[] args) {
        lc778 obj = new lc778();
        int[][] grid = {
            {0, 2},
            {1, 3}
        };
        int result = obj.swimInWater(grid);
        System.out.println(result); // 输出: 3
    }
}
